package graph;

import java.util.*;

/**
 * @ClassName LC210
 * @Description 拓扑排序模版题
 * @Author ZJX
 * @Date 2024/10/26 17:40
 * @Version 1.0
 */

//     https://leetcode.cn/problems/course-schedule-ii/description/
public class LC210 {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // 初始化图的邻接表和入度数组
        List<List<Integer>> adjList = new ArrayList<>();
        int[] inDegree = new int[numCourses];

        // 初始化邻接表
        for (int i = 0; i < numCourses; i++) {
            adjList.add(new ArrayList<>());
        }

        // 填充邻接表和入度数组
        for (int[] prerequisite : prerequisites) {
            int course = prerequisite[0];
            int prereq = prerequisite[1];
            adjList.get(prereq).add(course);
            inDegree[course]++;
        }

        // 创建一个队列用于存储入度为0的节点
        Queue<Integer> queue = new LinkedList<>();

        // 将所有入度为0的课程加入队列
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        // 存储拓扑排序的结果
        int[] order = new int[numCourses];
        int index = 0;

        // 进行拓扑排序
        while (!queue.isEmpty()) {
            int course = queue.poll();
            order[index++] = course;  // 将该课程加入到结果数组

            // 遍历当前课程的所有后续课程，将它们的入度减1
            for (int nextCourse : adjList.get(course)) {
                inDegree[nextCourse]--;
                // 如果某个课程的入度变为0，将它加入队列
                if (inDegree[nextCourse] == 0) {
                    queue.offer(nextCourse);
                }
            }
        }

        // 如果拓扑排序结果包含的课程数量不等于给定的课程数，说明有环
        if (index != numCourses) {
            return new int[0];
        }

        return order; // 返回拓扑排序后的课程顺序
    }

    public static void main(String[] args) {
        LC210 cs = new LC210();
        int numCourses = 4;
        int[][] prerequisites = {{1, 0}, {2, 0}, {3, 1}, {3, 2}};
        System.out.println(Arrays.toString(cs.findOrder(numCourses, prerequisites)));
    }
}
